/* 
 * Palindrome Partitioning
 */

#include "../func.h"

bool isPalindrome(string &s, int start, int end)
{
    while (start < end && s[start] == s[end])
    {
        ++start;
        --end;
    }
    return start >= end;
}
void DFS(string &s, vector<string> &path, vector<vector<string>> &result, int start)
{
    if (start == s.size())
    {
        result.push_back(path);
        return;
    }
    for (int i = start; i < s.size(); ++i)
    {
        if (isPalindrome(s, start, i))
        {
            path.push_back(s.substr(start, i - start + 1));
            DFS(s, path, result, i + 1);
            path.pop_back();
        }
    }
}

vector<vector<string>> partition2(string s)
{
    const int n = s.size();
    bool p[n][n];
    fill_n(&p[0][0], n * n, false);
    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
            p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]);

    vector<vector<string>> sub_palins[n];
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = i; j < n; ++j)
        {
            if (p[i][j])
            {
                string palindrome = s.substr(i, j - i + 1);
                if (j + 1 < n)
                {
                    for (auto v : sub_palins[j + 1])
                    {
                        v.insert(v.begin(), palindrome);
                        sub_palins[i].push_back(v);
                    }
                }
                else
                {
                    sub_palins[i].push_back(vector<string>{palindrome});
                }
            }
        }
    }
    return sub_palins[0];
}